package q33_search;

public class Solution {
    public int search(int[] nums, int target) {
        // 在该条件下，该数组要么只有一位数（=），要么就没有旋转（也就是在0处旋转），那么直接用二分查找就行
        if (nums[0] <= nums[nums.length - 1]) {
            return BinarySearch(nums, target);
        }
        if ((target < nums[0]) && (target > nums[nums.length - 1])) {
            return -1;
        }
        return search(nums, target, 0, nums.length - 1);
    }

    // 递归
    public int search(int[] nums, int target, int left, int right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        if (target == nums[left]) {
            return left;
        }
        if (target == nums[right]) {
            return right;
        }
        if (right - left == 1) {
            return target == nums[right] ? right : -1;
        }

        // 先判断在哪一侧,这里可以使用折线图可视化
        if (target > nums[left]) {

            if (nums[mid] > target) {
                return BinarySearch(nums, left, mid, target);
            } else if (nums[mid] < nums[right]) { // 这里肯定有nums[mid] < target
                right = mid;
                return search(nums, target, left, right);
            } else {
                left = mid;
                return search(nums, target, left, right);
            }
        } else if (target < nums[right]) {

            if (nums[mid] < target) {
                return BinarySearch(nums, mid, right, target);
            } else if (nums[mid] < nums[right]) { // 这里肯定有nums[mid] > target
                right = mid;
                return search(nums, target, left, right);
            } else {
                left = mid;
                return search(nums, target, left, right);
            }
        }
        return -1;
    }

    // 对于一个排序后数组的二分查找
    public int BinarySearch(int[] ary, int target) {
        return BinarySearch(ary, 0, ary.length - 1, target);
    }

    public int BinarySearch(int[] ary, int low, int high, int target) {
        if (high < low) return -1;
        int mid = low + ((high - low) >> 1);
        if (ary[mid] == target) return mid;
        if (ary[mid] > target) {
            return BinarySearch(ary, low, mid - 1, target);
        } else {
            return BinarySearch(ary, mid + 1, high, target);
        }
    }
}
